#!/usr/bin/python3
# -*- coding: utf-8 -*-
# @author: zzll0909
# @file: 744.py
# @time: 2025/1/23
# @software: PyCharm

from typing import List


class Solution:
    def nextGreatestLetter(self, letters: List[str], target: str) -> str:
        result = letters[0]
        if target < letters[-1]:
            lp = 0
            rp = len(letters) - 1
            while lp <= rp:
                mid = (lp + rp) // 2
                if letters[mid] <= target:
                    lp = mid + 1
                else:
                    rp = mid - 1
            result = letters[lp]
        return result


if __name__ == "__main__":
    pass
